package com.zzh.dp;
//在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
//
// 示例:
//
// 输入:
//
//1 0 1 0 0
//1 0 1 1 1
//1 1 1 1 1
//1 0 0 1 0
//
//输出: 4
// Related Topics 动态规划
// 👍 472 👎 0

public class No221_maximalSquare {
    public static void main(String[] args) {
        No221Solution solution = new No221Solution();
        int i = solution.maximalSquare(new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}});

        System.out.println(i);
    }
}

class No221Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int max = 0;
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                matrix[row][col] = (char) (matrix[row][col] - '0');
                if (col == 0 || row == 0) {
                    //啥也不做

                } else if (matrix[row][col] == 0) {
                    //啥也不做
                } else {
                    /*计算以matrix[row][col]为右下角的正方形个数*/
                    matrix[row][col] = (char) (threeMin(matrix[row - 1][col], matrix[row][col - 1], matrix[row - 1][col - 1]) + 1);
                }
                if (matrix[row][col] > max) {
                    max = matrix[row][col];
                }
            }
        }
        return max * max;
    }

    public char threeMin(char a, char b, char c) {
        return (char) Math.min(Math.min(a, b), c);
    }
}
